package dynamic;

import BranchBound.Task;

import java.util.Arrays;

public class IntervalScheduling {
    public int[] interval(Task[] tasks) {
        //位置position表示这个工作前面和最近并且相容的工作
        int[] position = new int[tasks.length];
        //根据结束时间排序
        Arrays.sort(tasks);
        for (int i = 1; i <= tasks.length - 1; i++) {
            //两两相容
            //进行比较如果能进行该工作，则记录下下一个工作的位置
            for (int j = i - 1; j > 0; j--) {
                if (tasks[j].getEnd() <= tasks[i].getStart()) {
                    position[i] = j;
                    break;
                }
            }
        }
        return position;
    }

    // 动态规划算法
    public int[][] solve(Task[] tasks, int[] position) {
        //权重
        int[] optimal = new int[tasks.length];
        //记录
        int[][] record = new int[tasks.length][2];
        for (int i = 1; i <= tasks.length - 1; i++) {
            //比较权值,如果这两个工作的权值比前面的大,选择该工作
            if (optimal[position[i]] + tasks[i].getWeight() >= optimal[i - 1]) {
                //更新权值
                optimal[i] = optimal[position[i]] + tasks[i].getWeight();

                record[i][0] = 1;
                record[i][1] = position[i];
            } else {
                optimal[i] = optimal[i - 1];
                record[i][0] = 0;
                record[i][1] = i - 1;
            }
        }
        return record;
    }
}
